using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using TrainGame.Common;
using TrainGame.Model;

namespace TrainGame.Engine.RouteCalc
{
	/// <summary>
	/// A collection of Routes; can represent all possible routes for a train, as well as a combination of 
	/// routes for the particluar trains a company is running.
	/// </summary>
	[Serializable]
	public class RouteCollection : ICollection
	{
		public int TotalValue
		{
			get
			{
				int total = 0;
				foreach (Route rt in _aRoutes)
					total += rt.Value;
				return (total);
			}
		}

		public int CachedTotalValue;	// used by route calculator
		public ulong[] ORedRouteBitArray;	// used by route calculator (this is all routes ORed together)
		public ushort[] BitsNotTouched;	// used by route calculator (byte MIGHT be big enough, but maybe not on a real complex map)

		private List<Route> _aRoutes;

		public Route this [int index]   // indexer declaration
		{ 
			get
			{
				return (Route) _aRoutes[index];
			}

			set
			{
				_aRoutes[index] = value;
			}
		}

		/// <summary>
		/// Treating the collection as a simple array turns out to be faster than List{Route}
		/// when caller repeatedly iterates through millions of routes
		/// </summary>
		/// <returns>array of routes - enjoy the perf boost!</returns>
		public Route[] GetAsArray()
		{
			return _aRoutes.ToArray();
		}

		public void CopyTo(Array a, int index)
		{
			_aRoutes.ToArray().CopyTo(a, index);
		}
		public object SyncRoot
		{
			get{return this;}
		}
		public bool IsSynchronized
		{
			get{return false;}
		}

		public int Count
		{
			get
			{
				return _aRoutes.Count;
			}
		}

		public RouteCollection ()
		{
			_aRoutes = new List<Route>();
		}
		public RouteCollection (RouteCollection source)
		{
			_aRoutes = new List<Route>(source._aRoutes);
		}

		public void SortHighestToLowest()
		{
			_aRoutes.Sort(new RouteSorter(true));
		}

		public void Add (Route Route)
		{
			_aRoutes.Add (Route);
		}

		public void AddRoutes (RouteCollection Routes)
		{
			foreach (Route route in Routes)
				Add (route);
		}

		public void AddNonConflictingRoutes (RouteCollection Routes)
		{
			foreach (Route route in Routes)
			{
				if (! route.ConflictsWith (this))
					Add (route);
			}
		}

		public void Remove (Route Route)
		{
			_aRoutes.Remove (Route);
		}


		// IEnumerable Interface Implementation:
		public IEnumerator GetEnumerator() // non-IEnumerable version
		{
			return _aRoutes.GetEnumerator ();
		}

		IEnumerator IEnumerable.GetEnumerator() // IEnumerable version
		{
			return _aRoutes.GetEnumerator ();
		}

		public override string ToString ()
		{
			StringBuilder sb = new StringBuilder ();
			if (_aRoutes.Count == 0)
				sb.Append ("No routes");
			else
			{
				for (int i=0; i < _aRoutes.Count; i++)
				{
					if (i > 0)
						sb.Append ("\n");
					((Route) _aRoutes[i]).ToString (sb);
				}
			}
			return sb.ToString ();
		}

		public string ToStringTerse(string lineBreak)
		{
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < _aRoutes.Count; i++)
			{
				if (i > 0)
					sb.Append(lineBreak);
				((Route)_aRoutes[i]).ToStringTerse(sb);
			}
			return sb.ToString();
		}

#if obsolete
		/// <summary>
		/// Find routes that are exact mirror images of each other, and remove one of them from the collection.
		/// </summary>
		public void RemoveMirrorRoutes()
		{
			List<Route> removeList = new List<Route>();
			long count = 0;
#if too_slow
			foreach (Route route in this)
			{
				foreach (Route test in this)
				{
					count++;
					if ((test != route) &&
						(!removeList.Contains(route)) &&
						(!removeList.Contains(test)) &&
						RouteCollection.AreMirrorRoutes(route, test))
					{
						removeList.Add(test);
						break;	// break here relies on only ONE potential mirror route in the collection
					}
				}
			}
#else
			// DONE: move this up into the route accumulation phase, because the Remove() below is taking a lot of time

			// build the hashtable, and at the same time discard mirror routes as they're found
			Dictionary<string, Route> routeHash = new Dictionary<string, Route>();
			foreach (Route route in this)
			{
				count++;
				string forward = route.GetRouteHash();
				string reverse = route.GetReverseRouteHash();

				if (routeHash.ContainsKey(forward) || routeHash.ContainsKey(reverse))
					removeList.Add(route);
				else
				{
					routeHash[forward] = route;
					routeHash[reverse] = route;

					// cache some values for faster routie combining
					route.CachedValue = route.Value;
#if obsolete
					ComputeRouteOverlapPoints(route);
#endif // obsolete
				}
			}
#endif
			foreach (Route route in removeList)
				this.Remove(route);		// would be better to never add them!
		}
#endif // obsolete

#if obsolete
		static private void ComputeRouteOverlapPoints(Route route)
		{
			route.OverlapPointHashList = new List<string>();
			foreach (TrackSegment ts in route.TrackSegments)
				AddTrackSegmentHashes(route.OverlapPointHashList, ts);
		}

		static private void AddTrackSegmentHashes(List<string> hashList, TrackSegment ts)
		{
			// for now we only care about hexside track connections
			// TODO: this doesn't handle city-to-city connections within the same hex (none in 1856)
			if (!ts.Start.AtCity)
			{
				hashList.Add(ts.Hex.Location + " " + ts.Start.Hexside);
				//ts.Start.HexsideInt = HexsideToInt(ts.Start.Hexside);
			}
			if (!ts.End.AtCity)
			{
				hashList.Add(ts.Hex.Location + " " + ts.End.Hexside);
				//ts.End.HexsideInt = HexsideToInt(ts.End.Hexside);
			}
		}
#endif // obsolete

		/// <summary>
		/// Print all the routes to the visual studio Output window.  Useful for debugging.
		/// </summary>
		public void DumpRoutes()
		{
			XTrace.Trace ("{0} routes:", this.Count);
			foreach (Route route in this._aRoutes)
				XTrace.Trace(route.ToString());
		}
	}

	[Serializable]
	public class Route
	{
		public Route()
		{
		}
		public Route(Route copyFrom)
		{
			Segments = (ArrayList)copyFrom.Segments.Clone();
		}

		public int CachedStops;			// used by route calculator

		public int Value
		{
			get
			{
				int val = 0;
				TrackSegment track;

				for (int i = 0; i < Segments.Count; i++)
				{
					track = (TrackSegment)Segments[i];
					if (track.Start.AtCity)
						val += track.Start.City.Value;
				}

				if (Segments.Count > 0)
				{
					track = (TrackSegment)Segments[Segments.Count - 1];
					if (track.End.AtCity)
						val += track.End.City.Value;
				}

				return val;
			}
		}

		private ArrayList Segments = new ArrayList();
		private TrackSegment[] CachedSegments = null;

		public int CachedValue;	// used by route calculator
#if obsolete
		public List<string> OverlapPointHashList;	// used by route calculator
#endif // obsolete
		public ulong[] TrackSegmentBitArray;	// used by route calculator

		public TrackSegment[] TrackSegments
		{
			get
			{
				if (CachedSegments == null)
				{
					CachedSegments = new TrackSegment[Segments.Count];
					for (int i = 0; i < Segments.Count; i++)
						CachedSegments[i] = (TrackSegment)Segments[i];
				}
				return CachedSegments;
			}
		}

		public void AddTrackSegment(TrackSegment ts)
		{
			Segments.Add(ts);
			CachedSegments = null;
		}

		public bool ContainsCity(City city)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (ts.ContainsCity(city))
					return true;
			return false;
		}

		public void TruncateToCity()
		{
			for (int i = Segments.Count - 1; i >= 0; i--)
			{
				if (((TrackSegment)Segments[i]).End.AtCity)
				{
					if (i < Segments.Count - 1)
					{
						Segments.RemoveRange(i + 1, Segments.Count - i - 1);
						CachedSegments = null;
					}
					return;
				}
			}
			Segments.RemoveRange(0, Segments.Count);
			CachedSegments = null;
		}

		public int Stops
		{
			get
			{
				int stops = 0;
				TrackSegment track;

				for (int i = 0; i < Segments.Count; i++)
				{
					track = (TrackSegment)Segments[i];
					if (track.Start.AtCity)
						stops++;
				}

				if (Segments.Count > 0)
				{
					track = (TrackSegment)Segments[Segments.Count - 1];
					if (track.End.AtCity)
						stops++;
				}

				return (stops);
			}
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder();
			ToString(sb);
			return sb.ToString();
		}

		public void ToString(StringBuilder sb)
		{
			sb.AppendFormat("{0} route({1}): ", Stops, Value);
			TrackSegment.ToString(TrackSegments, sb);
		}

		public void ToStringTerse(StringBuilder sb)
		{
			sb.AppendFormat("{0} route({1}): ", Stops, Value);
			// we'll only describe cities.  The first city in the route is a Start city, but all others will be End cities
			bool bStart = true;
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				if (bStart)
				{
					if (TrackSegments[i].Start.AtCity)
					{
						TrackSegment.ToString(sb, TrackSegments[i].Start);
						bStart = false;
					}
				}
				else
				{
					if (TrackSegments[i].End.AtCity)
					{
						sb.Append(" to ");
						TrackSegment.ToString(sb, TrackSegments[i].End);
					}
				}
			}
		}

		/// <summary>
		/// Get a unique ID for this route - guaranteed to be unique for the route
		/// </summary>
		/// <returns></returns>
		public string GetRouteID()
		{
			StringBuilder sb = new StringBuilder();
			GetRouteID(sb);
			return sb.ToString();
		}

		private void GetRouteID(StringBuilder sb)
		{
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				// conserve space!
				//if (i > 0)
				//	sb.Append(", ");
				//TrackSegments[i].ToString(sb);
				TrackSegments[i].ToStringSuperTerse(sb);
			}
		}

		/// <summary>
		/// Get a unique ID for the reverse of this route - guaranteed to be unique for the route,
		/// and guaranteed to match the ID of the reverse route
		/// </summary>
		/// <returns></returns>
		public string GetReverseRouteID()
		{
			StringBuilder sb = new StringBuilder();
			GetReverseRouteID(sb);
			return sb.ToString();
		}

		private void GetReverseRouteID(StringBuilder sb)
		{
			for (int i = TrackSegments.Length - 1; i >= 0; i--)
			{
				// conserve space!
				//if (i < TrackSegments.Length - 1)
				//	sb.Append(", ");
				//TrackSegments[i].ReverseToString(sb);
				TrackSegments[i].ReverseToStringSuperTerse(sb);
			}
		}

		public bool ContainsToken(PublicCompany company)
		{
			// can't use foreach since it walks the list backwards
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				TrackSegment ts = TrackSegments[i];
				if (ts.Start.AtCity)
				{
					foreach (Token token in ts.Hex.Tokens)
						if (token.Company == company)
						{
							// in cases like Toronto, we need to check whether the token is on the right side
							if (ts.Start.City.Hex.SeperateCities)
							{
								Side side = token.LocationInHex;
								string direction = side.Compass.ToString();
								if (CanTraceTrackToHexside(ts.Hex.TrackSegments, ts.Start, ts.End, direction))
									return true;
							}
							else
								return true;
						}
				}
			}
			// don't need to test every segment end, just the last one
			if (TrackSegments.Length > 0)
			{
				TrackSegment ts = TrackSegments[TrackSegments.Length - 1];
				if (ts.End.AtCity)
					foreach (Token token in ts.Hex.Tokens)
						if (token.Company == company)
						{
							// in cases like Toronto, we need to check whether the token is on the right side
							if (ts.End.City.Hex.SeperateCities)
							{
								Side side = token.LocationInHex;
								string direction = side.Compass.ToString();
								if (CanTraceTrackToHexside(ts.Hex.TrackSegments, ts.Start, ts.End, direction))
									return true;
							}
							else
								return true;
						}
			}
			return false;
		}

		static private bool CanTraceTrackToHexside(TrackSegment[] Segments, SegmentEndpoint startPoint, SegmentEndpoint endPoint, string endHexside)
		{
			if ((!startPoint.AtCity) && (startPoint.Hexside == endHexside))
				return true;
			if ((!endPoint.AtCity) && (endPoint.Hexside == endHexside))
				return true;
			//if (! endPoint.AtCity)
			//	return (endPoint.Hexside == endHexside);
			//if ((! endPoint.AtCity) && (endPoint.Hexside == endHexside))
			//	return true;
			City city = (startPoint.AtCity) ? startPoint.City : endPoint.City;
			if (city == null)
				return false;
			for (int i = 0; i < Segments.Length; i++)
			{
				TrackSegment ts = Segments[i];
				SegmentEndpoint newStart, newEnd;
				if (ts.StartsAtCity(city, out newStart, out newEnd))
				{
					if ((newStart != startPoint) && (newStart != endPoint))
					{
						if (newEnd.AtCity)
						{
							if (CanTraceTrackToHexside(Segments, newStart, newEnd, endHexside))
								return true;
						}
						else if (newEnd.Hexside == endHexside)
							return true;
					}
				}
			}
			return false;
		}

		public bool ConflictsWith(TrackSegment track)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (ts.OverlapsWith(track))
					return true;
			return false;
		}

		public bool ConflictsWith(Route route)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (route.ConflictsWith(ts))
					return true;
			return false;
		}

		public Route FindConflictingRoute(RouteCollection routeCollection)
		{
			foreach (Route route in routeCollection)
				if (this.ConflictsWith(route))
					return route;
			return null;
		}

		public bool ConflictsWith(RouteCollection routeCollection)
		{
			return (null != FindConflictingRoute(routeCollection));
		}

#if obsolete
		// try inlining the whole thing
		public bool InlinedConflictsWith(RouteCollection routeCollection)
		{
			foreach (Route route in routeCollection)
			{
				if (InlinedConflictsWith(route))
					return true;
			}
			return false;
		}

		public bool InlinedConflictsWith(Route route)
		{
			foreach (TrackSegment ts in this.TrackSegments)
				foreach (TrackSegment segment in route.TrackSegments)
				{
					//if (ts.OverlapsWith(segment))
					//	return true;

					// this inner logic is copied from TrackSegment.OverlapsWith
					if (ts.Hex == segment.Hex)
					{
						// no city-to-city segments in 1856, so this first if() is never taken in 1856
						if (ts.Start.AtCity && ts.End.AtCity)
						{
							//
							//  If city to city connection, they both have to match (in either order)
							//
							if (segment.Start.AtCity && segment.End.AtCity)
							{
								//if ( (Start.City.Equals (segment.Start.City) && End.City.Equals (segment.End.City)) ||
								//  (Start.City.Equals (segment.End.City) && End.City.Equals (segment.Start.City)))
								if (((ts.Start.City == segment.Start.City) && (ts.End.City == segment.End.City)) ||
									((ts.Start.City == segment.End.City) && (ts.End.City == segment.Start.City)))
									return true;
							}
						}
#if not_unrolled
							else if (!(segment.Start.AtCity && segment.End.AtCity))
							{
								if (!ts.Start.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.Start.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.Start.Hexside == segment.Start.Hexside))
											return true;
									}
									if (!segment.End.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.End.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.Start.Hexside == segment.End.Hexside))
											return true;
									}
								}
								if (!ts.End.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.Start.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.End.Hexside == segment.Start.Hexside))
											return true;
									}
									if (!segment.End.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.End.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.End.Hexside == segment.End.Hexside))
											return true;
									}
								}
							}
#endif // not_unrolled
						// unroll into separate tests to eliminate the duplicate segment.X.AtCity tests
						// (yes, this is ugly and hard to understand now)
						// (and it only saves about 3% in the CGR test - 34.9 vs. 36.4 seconds)
						else
						{
							if (!segment.Start.AtCity)
							{
								if (!ts.Start.AtCity)
								{
									if (ts.Start.Hexside == segment.Start.Hexside)
										return true;
									if (!segment.End.AtCity)
									{
										if (ts.Start.Hexside == segment.End.Hexside)
											return true;
									}
								}
								if (!ts.End.AtCity)
								{
									if (ts.End.Hexside == segment.Start.Hexside)
										return true;
									if (!segment.End.AtCity)
									{
										if (ts.End.Hexside == segment.End.Hexside)
											return true;
									}
								}
							}
							else if (!segment.End.AtCity)
							{
								if (!ts.Start.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										if (ts.Start.Hexside == segment.Start.Hexside)
											return true;
									}
									if (ts.Start.Hexside == segment.End.Hexside)
										return true;
								}
								if (!ts.End.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										if (ts.End.Hexside == segment.Start.Hexside)
											return true;
									}
									if (ts.End.Hexside == segment.End.Hexside)
										return true;
								}
							}
						}
					}
				}
			return false;
		}
#endif // obsolete
	}

	public class RouteSorter : IComparer<Route>
	{
		public bool HighestFirst = true;

		public RouteSorter(bool highestFirst)
		{
			HighestFirst = highestFirst;
		}

	#region IComparer<Route> Members
		/// <summary>
		/// Compares two routes based on their .CachedValue member.
		/// 
		/// This function respects the HighestFirst member variable.
		/// Use it to force highest-first or lowest-frist sorting.
		/// </summary>
		/// <param name="x"></param>
		/// <param name="y"></param>
		/// <returns>
		///		-1 for x-before-y
		///		+1 for y-before-x
		///		 0 for x = y
		/// </returns>
		public int Compare(Route x, Route y)
		{
			if (x.CachedValue == y.CachedValue)
				return 0;

			if (HighestFirst)
			{
				// we want the better route
				if (x.CachedValue > y.CachedValue)
					return -1;	// x is higher value route
				return +1;		// y is higher value route
			}
			else
			{
				// we want the worse route
				if (x.CachedValue < y.CachedValue)
					return -1;	// x is lower value route
				return +1;		// y is lower value route
			}
		}
	#endregion
	}
}

namespace TrainGame.Model
{
    [Serializable]
    public class City
    {
        public GameboardHex Hex = null;
        public string Name;
        public bool Offboard = false;
        public int Value { get { return Hex.Value; } }
        public int Tokens { get { return CalcCityCurrentTokens(); } }
        public int TokenSpots { get { return CalcCityMaxTokens(Hex); } }
        public GameboardHex.eTownType CityType
        {
            get
            {
                if (Hex.Tile != null)
                    return Hex.Tile.TownType;
                return Hex.TownType;
            }
        }

        //public List<Side.CompassDirection> HexsidesConnectsTo = new List<Side.CompassDirection>();
        public ArrayList HexsidesConnectsTo = new ArrayList();

        public bool Equals(City testCity)
        {
            return (this == testCity);
        }

        public override string ToString()
        {
            if (Hex.Tile == null)
                return string.Format("{0} in hex {1}", Name, Hex.Location);
            return string.Format("{0} in hex {1} tile {2}", Name, Hex.Location, Hex.Tile.Name);
        }

        static public City[] GetAllCities(Gameboard gameboard, PublicCompany company)
        {
            ArrayList cities = new ArrayList();
            foreach (GameboardHex hex in gameboard.GameboardHexes)
            {
                if (hex.Cities != null)
                    foreach (City city in hex.Cities)
                        cities.Add(city);
            }
            City[] ca = new City[cities.Count];
            for (int i = 0; i < cities.Count; i++)
                ca[i] = (City)cities[i];
            return (ca);
        }

        static public City[] GetAllTokenedCities(PublicCompany company)
        {
            ArrayList cities = new ArrayList();
            foreach (GameboardHex hex in company.TokenHexes)
            {
                if (hex.Cities != null)
                    // NOT QUITE CORRECT YET
                    foreach (City city in hex.Cities)
                        cities.Add(city);
            }
            City[] ca = new City[cities.Count];
            for (int i = 0; i < cities.Count; i++)
                ca[i] = (City)cities[i];
            return (ca);
        }

        private int CalcCityCurrentTokens()
        {
            // if there's only a single city, it's easy
            if (!Hex.SeperateCities)
                return Hex.Tokens.Count;

            // otherwise we need to check each token to see if it's in this city or the other one
            int count = 0;
            foreach (Token token in Hex.Tokens)
            {
                if (this.HexsidesConnectsTo.Contains(token.LocationInHex.Compass))
                    count++;
            }
            return count;
        }

        static public int CalcCityMaxTokens(GameboardHex hex)
        {
            // this is a max max count not a current max count
            int nMaxTokens = hex.MaxTokens;

            if (hex.Tile == null)
                return Math.Min(nMaxTokens, 1);

            // temp hack taken from OperatingRound2.PlaceToken
            if (hex.Tile.TownType == GameboardHex.eTownType.City)
            {
                switch (hex.Tile.Color)
                {
                    case Tile.eTileColor.Yellow:
                        nMaxTokens = 1;
                        break;

                    case Tile.eTileColor.Green:
                        nMaxTokens = 2;

                        if ((hex.City == "Toronto") || (hex.City == "New York"))
                            nMaxTokens = 1;
                        break;

                    case Tile.eTileColor.Brown:
                        if (hex.SeperateCities)
                            nMaxTokens = 1;
                        else
                            nMaxTokens = 2;

                        // NO - for route purposes, Toronto is two 2-spot cities
                        //if ((hex.City == "Toronto") || (hex.City == "New York"))
                        //	nMaxTokens = 4;
                        break;

                    case Tile.eTileColor.Gray:
                        break;
                }
            }
            return nMaxTokens;
        }
    }

    [Serializable]
    public class TrackSegment
    {
        public GameboardHex Hex = null;
        public SegmentEndpoint Start = null;
        public SegmentEndpoint End = null;

        public TrackSegment()
        {
            Start = new SegmentEndpoint();
            End = new SegmentEndpoint();
        }

        public TrackSegment(GameboardHex hex, SegmentEndpoint start, SegmentEndpoint end)
        {
            Hex = hex;
            Start = new SegmentEndpoint(start);
            End = new SegmentEndpoint(end);
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            ToString(sb);
            return sb.ToString();
        }

        public void ToString(StringBuilder sb)
        {
            ToString(sb, Start);
            sb.Append(" to ");
            ToString(sb, End);
        }

        public void ToStringSuperTerse(StringBuilder sb)
        {
            ToStringSuperTerse(sb, Start);
            ToStringSuperTerse(sb, End);
        }

        public void ReverseToString(StringBuilder sb)
        {
            ToString(sb, End);
            sb.Append(" to ");
            ToString(sb, Start);
        }

        public void ReverseToStringSuperTerse(StringBuilder sb)
        {
            ToStringSuperTerse(sb, End);
            ToStringSuperTerse(sb, Start);
        }

        static public void ToString(StringBuilder sb, SegmentEndpoint point)
        {
            if (point.AtCity)
            {
                if (point.City.Name.Length > 0)
                    sb.Append(point.City.Name);
                else if ((point.City.Hex.Tile != null) && (point.City.Hex.Tile.TownType == GameboardHex.eTownType.Town))
                    sb.AppendFormat("Town {0}", point.City.Hex.Location);
                else if (point.City.Hex.TownType == GameboardHex.eTownType.Town)
                    sb.AppendFormat("Town {0}", point.City.Hex.Location);
                else
                    sb.AppendFormat("City {0}", point.City.Hex.Location);
                sb.AppendFormat(" ({0})", point.City.Value);
            }
            else
                sb.AppendFormat("{0}", point.Hexside);
        }

        static public void ToStringSuperTerse(StringBuilder sb, SegmentEndpoint point)
        {
            if (point.AtCity)
                sb.AppendFormat(point.City.Hex.Location);
            else
                sb.AppendFormat(point.Hexside);
        }

        // ToString an array of TrackSegments
        static public string ToString(TrackSegment[] TrackSegments)
        {
            if ((TrackSegments == null) || (TrackSegments.Length == 0))
                return "[empty]";
            StringBuilder sb = new StringBuilder();
            ToString(TrackSegments, sb);
            return sb.ToString();
        }
        static public void ToString(TrackSegment[] TrackSegments, StringBuilder sb)
        {
            for (int i = 0; i < TrackSegments.Length; i++)
            {
                if (i > 0)
                    sb.Append(", ");
                TrackSegments[i].ToString(sb);
            }
        }

        public bool StartsAtCity(City city, out SegmentEndpoint startEndpoint, out SegmentEndpoint endEndpoint)
        {
            bool Use = false;
            startEndpoint = null;
            endEndpoint = null;
            if (Start.AtCity && Start.City.Equals(city))
            {
                Use = true;
                startEndpoint = Start;
                endEndpoint = End;
            }
            else if (End.AtCity && End.City.Equals(city))
            {
                Use = true;
                startEndpoint = End;
                endEndpoint = Start;
            }
            return (Use);
        }

        public bool StartsAtHexside(string direction, out SegmentEndpoint startEndpoint, out SegmentEndpoint endEndpoint)
        {
            bool Use = false;
            startEndpoint = null;
            endEndpoint = null;
            if ((!Start.AtCity) && (Start.Hexside == direction))
            {
                Use = true;
                startEndpoint = Start;
                endEndpoint = End;
            }
            else if ((!End.AtCity) && (End.Hexside == direction))
            {
                Use = true;
                startEndpoint = End;
                endEndpoint = Start;
            }
            return (Use);
        }

        public bool ContainsCity(City city)
        {
            return (Start.AtCity && Start.City.Equals(city)) || (End.AtCity && End.City.Equals(city));
        }

        /// <summary>
        /// Returns true if either end of the track segment hits the same hexside. Use this to prevent
        /// train routes from sharing track.
        /// </summary>
        /// <param name="segment"></param>
        /// <returns></returns>
        public bool OverlapsWith(TrackSegment segment)
        {
            //
            // if (city to city connection) 
            //	 if both cities match (in either order), return true 
            //	 else return false 
            // else 
            //	 if any segment hexside matches any this hexside, return true 
            //	 else return false
            //
            if (Hex != segment.Hex)
                return false;
            if (Start.AtCity && End.AtCity)
            {
                //
                //  If city to city connection, they both have to match (in either order)
                //
                if (segment.Start.AtCity && segment.End.AtCity)
                {
                    //if ( (Start.City.Equals (segment.Start.City) && End.City.Equals (segment.End.City)) ||
                    //  (Start.City.Equals (segment.End.City) && End.City.Equals (segment.Start.City)))
                    if (((Start.City == segment.Start.City) && (End.City == segment.End.City)) ||
                      ((Start.City == segment.End.City) && (End.City == segment.Start.City)))
                        return true;
                }
            }
            else if (!(segment.Start.AtCity && segment.End.AtCity))
            {
                if (!Start.AtCity)
                {
                    if (!segment.Start.AtCity)
                    {
                        //if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.Start.Hexside))
                        if (/*(Hex == segment.Hex) &&*/ (Start.Hexside == segment.Start.Hexside))
                            return true;
                    }
                    if (!segment.End.AtCity)
                    {
                        //if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.End.Hexside))
                        if (/*(Hex == segment.Hex) &&*/ (Start.Hexside == segment.End.Hexside))
                            return true;
                    }
                }
                if (!End.AtCity)
                {
                    if (!segment.Start.AtCity)
                    {
                        //if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.Start.Hexside))
                        if (/*(Hex == segment.Hex) &&*/ (End.Hexside == segment.Start.Hexside))
                            return true;
                    }
                    if (!segment.End.AtCity)
                    {
                        //if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.End.Hexside))
                        if (/*(Hex == segment.Hex) &&*/ (End.Hexside == segment.End.Hexside))
                            return true;
                    }
                }
            }
            return false;
        }

        /// <summary>
        /// Returns true if the track segments are the same. Use this to prevent adding the same segment
        /// (in either direction) to the same collection twice.
        /// </summary>
        /// <param name="segment"></param>
        /// <returns></returns>
        public bool IsSameSegment(TrackSegment segment)
        {
            bool SameStart = false;
            bool SameEnd = false;
            bool Reverse = false;

            // do they share the same start point?
            if (Start.AtCity)
            {
                if (segment.Start.AtCity && (Start.City == segment.Start.City))
                    SameStart = true;
                else if (segment.End.AtCity && (Start.City == segment.End.City))
                {
                    Reverse = true;
                    SameStart = true;
                }
            }
            else
            {
                if ((!segment.Start.AtCity) && (Start.Hexside == segment.Start.Hexside))
                    SameStart = true;
                else if ((!segment.End.AtCity) && (Start.Hexside == segment.End.Hexside))
                {
                    Reverse = true;
                    SameStart = true;
                }
            }

            // do they share the same end point?
            if (End.AtCity)
            {
                if ((!Reverse) && segment.End.AtCity && (End.City == segment.End.City))
                    SameEnd = true;
                else if (Reverse && segment.Start.AtCity && (End.City == segment.Start.City))
                    SameEnd = true;
            }
            else
            {
                if ((!Reverse) && (!segment.End.AtCity) && (End.Hexside == segment.End.Hexside))
                    SameEnd = true;
                else if (Reverse && (!segment.Start.AtCity) && (End.Hexside == segment.Start.Hexside))
                    SameEnd = true;
            }

            return SameStart && SameEnd;
        }

        /// <summary>
        /// Call this function for a hex after placing a new tile there.
        /// </summary>
        /// <param name="hex">Writes the hex.Cities and hex.TrackSegments members</param>
        static public void CalculateHexRoutes(GameboardHex hex)
        {
            CalculateHexRoutes(hex, hex.ExistingRoutes);
        }
        static public void CalculateHexRoutesFromNewRoutes(GameboardHex hex)
        {
            CalculateHexRoutes(hex, hex.NewRoutes);
        }
        static private void CalculateHexRoutes(GameboardHex hex, Hashtable HexRoutesTable)
        {
            City city;
            ArrayList Segments = new ArrayList();

            if (hex.HexType == GameboardHex.eHexType.OffBoard)
            {
                hex.Cities = new City[1];
                city = new City();
                city.Hex = hex;
                city.Offboard = true;
                city.Name = MakeCityName(hex);
                //city.Tokens = hex.Tokens.Count;
                //city.TokenSpots = CalcCityTokens(hex);
                //city.Value = hex.Value;
                hex.Cities[0] = city;

                foreach (string side in hex.Neighbors.Keys)
                {
                    TrackSegment ts = new TrackSegment();
                    ts.Hex = hex;
                    ts.Start.AtCity = true;
                    ts.Start.City = city;

                    ts.End.AtCity = false;
                    ts.End.Hexside = side;

                    if (!SameSegmentInCollection(ts, Segments))
                        Segments.Add(ts);
                }
            }
            else
            {
                //
                // create cities
                //
                int citycount = 0;
                GameboardHex.eTownType townType = (hex.Tile == null) ? hex.TownType : hex.Tile.TownType;
                if (townType != GameboardHex.eTownType.None)
                {
                    // eTownType.Town = 1 town
                    // eTownType.DblTown = 2 towns
                    // eTownType.City && (! SeperateCities) = 1 city
                    // eTownType.City && SeperateCities = 2 cities
                    string whichCity = null;
                    citycount = (townType == GameboardHex.eTownType.DblTown) ? 2 : 1;
                    if ((citycount == 1) && hex.SeperateCities &&
                        // TODO: HACK for Gray Toronto!  Fix this more generally (tiles should probably have a SeperateCity bool to override hex's value
                      ((hex.Tile == null) || (hex.Tile.Name != "124")))
                        citycount = 2;
                    if (citycount == 2)
                        whichCity = " A";

                    hex.Cities = new City[citycount];

                    // create the (first) city for this hex
                    city = new City();
                    city.Hex = hex;
                    city.Name = MakeCityName(hex, whichCity);
                    //city.Tokens = hex.Tokens.Count;
                    //city.TokenSpots = CalcCityTokens(hex);
                    //city.Value = hex.Value;
                    hex.Cities[0] = city;

                    if (citycount == 2)
                    {
                        // create the second city for this hex
                        city = new City();
                        city.Hex = hex;
                        whichCity = " B";
                        city.Name = MakeCityName(hex, whichCity);
                        //city.Tokens = hex.Tokens.Count;
                        //city.TokenSpots = CalcCityTokens(hex);
                        //city.Value = hex.Value;
                        hex.Cities[1] = city;
                    }
                }

                //
                // connect hexsides to cities or other hexsides
                //
                //int citynum = 0;
                //int segmentNum = 0;
                foreach (Side startSide in HexRoutesTable.Keys)
                {
                    SideCollection endSides = HexRoutesTable[startSide] as SideCollection;

                    if (endSides.Count == 0)
                    {
                        // track goes from side to city, eg. yellow Toronto starting tile
                        TrackSegment ts = new TrackSegment();
                        ts.Hex = hex;
                        ts.Start.AtCity = false;
                        ts.Start.Hexside = startSide.GetDirection();

                        ts.End.AtCity = true;
                        ts.End.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, startSide, null);

                        //FixCityName (hex.Cities[citynum], ts.Start.Hexside);

                        if (!SameSegmentInCollection(ts, Segments))
                            Segments.Add(ts);

                        //if (citynum < citycount - 1)
                        //	citynum++;
                    }
                    else
                    {
                        //citynum = 0;
                        foreach (Side side in endSides)
                        {
                            TrackSegment ts = new TrackSegment();
                            ts.Hex = hex;
                            ts.Start.AtCity = false;
                            ts.Start.Hexside = startSide.GetDirection();

                            if (townType == GameboardHex.eTownType.None)
                            {
                                ts.End.AtCity = false;
                                ts.End.Hexside = side.GetDirection();

                                if (!SameSegmentInCollection(ts, Segments))
                                    Segments.Add(ts);
                            }
                            else
                            {
                                ts.End.AtCity = true;
                                ts.End.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, startSide, side);

                                //FixCityName (hex.Cities[citynum], ts.Start.Hexside);

                                if (!SameSegmentInCollection(ts, Segments))
                                    Segments.Add(ts);

                                ts = new TrackSegment();
                                ts.Hex = hex;
                                ts.Start.AtCity = true;
                                ts.Start.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, side, startSide);

                                ts.End.AtCity = false;
                                ts.End.Hexside = side.GetDirection();

                                //FixCityName (hex.Cities[citynum], ts.End.Hexside);

                                if (!SameSegmentInCollection(ts, Segments))
                                    Segments.Add(ts);

                                // JoeB NOTE: Double-town tiles will not work right unless
                                // the "same-city" segments are next to each other in the list.
                                // DO NOT MIX THEM.
                                //if (++segmentNum == 2)
                                //{
                                //	segmentNum = 0;
                                //	if (citynum < hex.Cities.Length - 1)
                                //		citynum++;
                                //}
                            }
                        }
                    }
                }
            }

            //hex.TrackSegments = new TrackSegment[Segments.Count];
            //for (int i=0; i < Segments.Count; i++)
            //	hex.TrackSegments[i] = (TrackSegment) Segments [i];
            hex.TrackSegments = (TrackSegment[])Segments.ToArray(typeof(TrackSegment));
        }

        static private City WhichCityDoesHexsideConnectTo(GameboardHex hex, Side thisSide, Side destSide)
        {
            // find the city that already connects to this hexside
            City firstNullCity = null;
            foreach (City testCity in hex.Cities)
            {
                if ((testCity.HexsidesConnectsTo.Count == 0) && (firstNullCity == null))
                    firstNullCity = testCity;
                foreach (Side.CompassDirection testSide in testCity.HexsidesConnectsTo)
                {
                    if (testSide == thisSide.Compass)
                        return testCity;
                    if ((destSide != null) && (testSide == destSide.Compass))
                    {
                        if (!testCity.HexsidesConnectsTo.Contains(thisSide.Compass))
                            testCity.HexsidesConnectsTo.Add(thisSide.Compass);
                        return testCity;
                    }
                }
            }

            // if none found, add it to the first city with no hexside connections
            if (firstNullCity != null)
            {
                firstNullCity.HexsidesConnectsTo.Add(thisSide.Compass);
                return firstNullCity;
            }

            // if still none found, just make it the first city
            City city = hex.Cities[0];
            city.HexsidesConnectsTo.Add(thisSide.Compass);
            return city;
        }

        static internal string MakeCityName(GameboardHex hex)
        {
            return MakeCityName(hex, null);
        }

        static private string MakeCityName(GameboardHex hex, string whichCity)
        {
            if (hex.City.Length > 0)
                return hex.City + whichCity;
            GameboardHex.eTownType townType = (hex.Tile == null) ? hex.TownType : hex.Tile.TownType;
            if (townType == GameboardHex.eTownType.City)
                return string.Format("City{0} {1}", whichCity, hex.Location);
            return string.Format("Town{0} {1}", whichCity, hex.Location);
        }

        // JoeB: Used to be called ConflictingSegmentInCollection, but that would incorrectly reject multiple
        // track segments in a green or brown tile that share one endpoint but not the other.  We still need
        // to check for duplciate segments because
        //static private bool ConflictingSegmentInCollection(TrackSegment ts, ArrayList Segments)
        //{
        //    foreach (TrackSegment track in Segments)
        //        if (ts.OverlapsWith (track))
        //            return true;
        //    return false;
        //}
        static private bool SameSegmentInCollection(TrackSegment ts, ArrayList Segments)
        {
            foreach (TrackSegment track in Segments)
                if (ts.IsSameSegment(track))
                    return true;
            return false;
        }

        static public TrackSegment[] GetNonMatchingTrackSegments(TrackSegment[] originalSegments, TrackSegment[] newSegments)
        {
            // returns those segements in newSegments that are not in originalSegments 
            ArrayList list = new ArrayList();

            foreach (TrackSegment test in newSegments)
            {
                bool InOrig = false;
                foreach (TrackSegment orig in originalSegments)
                {
                    if (orig == test)
                    {
                        InOrig = true;
                        break;
                    }
                }
                if (!InOrig)
                    list.Add(test);
            }

            TrackSegment[] NonMatching = new TrackSegment[list.Count];
            for (int i = 0; i < list.Count; i++)
                NonMatching[i] = (TrackSegment)list[i];
            return NonMatching;
        }
    }

    [Serializable]
    public class SegmentEndpoint
    {
        public bool AtCity = false;
        public City City = null;
        public string Hexside = "";

        public bool AtTown
        {
            get
            {
                return AtCity &&
                    (City.CityType == GameboardHex.eTownType.Town) || (City.CityType == GameboardHex.eTownType.DblTown);
            }
        }

        public int HexsideId;	// used by route calculator

        public SegmentEndpoint()
        {
        }

        public SegmentEndpoint(SegmentEndpoint copy)
        {
            AtCity = copy.AtCity;
            City = copy.City;
            Hexside = copy.Hexside;
        }
    }
}